//Astar专用,全局变量
PriorityQueue<PII> heap = new PriorityQueue<PII>();

static int N = 200010;
static int[] dist = new int[N];
static int INF = 0x3f3f3f3f;//设置无穷大


int f(int t){
    int x = t % cols,y = t / cols;
    return abs(width  - y - 1) + abs(height  - x - 1) ;
}

void Astar() {
    if (heap.size() > 0 ) {
  
          PII t = heap.peek();//返回顶端
          int ver = t.getSecond();
          int distance = dist[ver];//要真实距离，不是t.first
        
          if(ver == cols * rows - 1 ){
              current = grid[ver];//没有这一步，Astar路径长度从起点的前一个点开始计算
              findpath = true;
              println("Found!");
              println("steps:" + steps);
              drawWindow(1);
              return;
          }
          heap.remove();
          current = grid[ver];
     
          ArrayList<Cell> neighbours = current.neighbours;
          for (Cell neighbour : neighbours) {
              int state = neighbour.i + neighbour.j * cols;
              if (!neighbour.visited || dist[state] > distance + 1) {
                  neighbour.visited = true;
                  neighbour.previous = current;
                  dist[state] = distance + 1;//!更新距离
                  heap.add(new PII (dist[state] + f(state),state));
                  //route
              }
          }
        
        drawWindow(1);

    } else{
        println("No solution_Astar");
        drawWindow(1);
        noLoop();
        return;
    }
    delay(delay_t);

    // backtrack不能放这里是因为当current==end就到不了这里，从而触发不了backtrack，
    //进而不能触发backtrack里面的绘制回溯路径
}
